package phaseI;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;


public class DFATable extends NFATable {
	protected Hashtable<String,Hashtable<String,ArrayList<String>>> finalstates;

	public DFATable() {
		super();
	}
	
	public String getStateFromTransition(String prevState, String transition)
	{
		ArrayList<String> stateList = super.getStatesFromTransition(prevState, transition);
		if(stateList == null)
			return null;
		//At most one state is possible given a specific transition in a DFA
		return super.getStatesFromTransition(prevState, transition).get(0);
		
	}
	
	public static DFATable convertFromNFA (NFATable nfa) 
	{	
		//current state, next state, transition
		String currentState = "1";
		Hashtable<String,Hashtable<String,ArrayList<String>>> table = nfa.getTable();
		LinkedList<String> futureStatesQueue = new LinkedList<String>();
		futureStatesQueue.add(currentState);
		
		DFATable result = new DFATable();
		String newState = "";
		
		StringTokenizer stk = null;
		
		ArrayList<String> transList = nfa.getStateTransitions();
		ArrayList<String> whereIveBeen = new ArrayList<String>();
		whereIveBeen.add(currentState);
//		for(String endState : nfa.getEndStates())
//		{
//			whereIveBeen.add(endState);
//		}
		
		while(!futureStatesQueue.isEmpty())
		{
			currentState = futureStatesQueue.pop();
			stk = new StringTokenizer(currentState,";");
			while(stk.hasMoreTokens())
			{	
				String stringStateIter = stk.nextToken();
				//System.out.println(currentState);
				Hashtable<String,ArrayList<String>> trans = table.get(stringStateIter);
				Hashtable<String,Hashtable<String,ArrayList<String>>> retable = result.getTable();
				String epsStates = "";
				
				if(trans!=null && trans.get("epsilon")!=null)
				{
					for(String state : trans.get("epsilon"))
					{
						epsStates+=state + ";";
					}
					epsStates = epsStates.substring(0,epsStates.length()-1);
					for(String tra : transList)
					{
						if(!tra.equals("epsilon")){
//							System.out.println(currentState);
//							StringTokenizer stk2 = new StringTokenizer(epsStates,";");
//							while(stk2.hasMoreTokens())
//							{
								//retable.get(currentState).get(tra).add(stk2.nextToken());
//								result.addTransition(currentState, stk2.nextToken(), tra);
//							}
							String normalStates = "";
							if(trans.get(tra)!=null)
							{
								for(String state: trans.get(tra))
									normalStates+=state + ";";
							}
							
							result.addTransition(currentState,normalStates+epsStates, tra);
							for(String endState : nfa.getEndStates())
							{
								if((normalStates+epsStates).contains(endState) && !result.getEndStates().contains((normalStates+epsStates)))
									result.addEndState((normalStates+epsStates));
							}
							if(!whereIveBeen.contains(normalStates+epsStates))
							{
								futureStatesQueue.add(normalStates+epsStates);
								whereIveBeen.add(normalStates+epsStates);
							}
						}
					
	
					}
				}
				else if(trans!=null)
				{
					Iterator<Map.Entry<String,ArrayList<String>>> iterTrans = trans.entrySet().iterator();
					while(iterTrans.hasNext())
					{
	//					System.out.println("RAN");
						newState = "";
						
						Map.Entry<String,ArrayList<String>> entry = iterTrans.next();
						
						if(!entry.getKey().equals("epsilon"))
						{
							for(String futureState : entry.getValue())
							{
								newState += futureState + ";";	
							}
							newState = newState.substring(0,newState.length()-1);
							if(!whereIveBeen.contains(newState))
							{
								futureStatesQueue.add(newState);
								whereIveBeen.add(newState);
							}
	//						System.out.println(futureStatesQueue);
							//System.out.println(currentState + " " + newState + " " + entry.getKey());
							//System.out.println(result);
							if(result.getStatesFromTransition(currentState, entry.getKey())==null||!result.getStatesFromTransition(currentState, entry.getKey()).contains(newState))
							{
								result.addTransition(currentState, newState, entry.getKey());
								for(String endState : nfa.getEndStates())
								{
									if(newState.contains(endState) && !result.getEndStates().contains(newState))
										result.addEndState(newState);
								}
							}
							
	//						System.out.println("RAN");
						}
						else
						{
							
							ArrayList<String> alist = entry.getValue();
							for(String state : alist){
								if(!whereIveBeen.contains(state)){
									futureStatesQueue.add(state);
									whereIveBeen.add(state);
								}
							}
						}
					}
				}
//				if(trans!=null && currentState.contains(";"))
//				{
//					
//				}
			}
		}

		return result;
	}
	

}
